특정 키값이 출현하는 빈도를 저장하여 누적분포를 이용하여 간단하게 정렬하는 방법이다.
누적분포
배열을 어떻게 정렬하는 지 본격적으로 알아보자
키 값이 1에서 5까지만의 값을 가지는 a[]라는 정수 배열을 정렬해 보자
1 3 2 2 3 1 3 2 4 2 4 3 1 2 1 2 5 1 5 3
count[1] = 5
count[2] = 6
count[3] = 5
count[4] = 2
count[5] = 2
count[1] = 5
count[2] = count[2] + count[1] = 11
count[3] = count[3] + count[2] = 16
count[4] = count[4] + count[3] = 18
count[5] = count[5] + count[4] = 20
분포수세기 알고리즘은 안정성(statbility)에 있다. 그래서 a[] 배열에서 값을 꺼내올 때 뒤에서부터 꺼낸다.
그림 참조
package com.oracleclub.study.algorithm;
import org.junit.Test;
public class DistributionCountingTest {
@Test
public void distributionCounting_test() {
int[] a = {1, 3, 4, 2, 3};
int[] b = distributionCounting(a, 5, 4);
for (int i = 0; i < b.length; i++) {
System.out.println("b[" + i + "]=" + b[i]);
}
}
/**
*
* @param a
* @param n 입력인자 a[] 배열이 가지는 개수
* @param m a[] 배열이 가지는 키 값의 범위
*/
private int[] distributionCounting(int a[], int n, int m) {
int[] b = new int[n]; // 정렬 결과를 담을 변수
int[] count = new int[m + 1]; //1. count[] 배열 선언 및 초기화
// 2. 배열 a[]에서 키의 빈도수를 계산하여 count[]에 저장
for (int i = 0; i < n; i++) {
++count[a[i]];
}
// 3. count[] 배열을 누적분포로 변환
for (int i = 1; i <= m; i++) {
count[i] += count[i-1];
}
// 4. a[] 배열을 뒤에서부터 읽어서 배열 b[--count[a[i]]]에 저장
for (int i = n - 1; i >= 0; i--) {
b[--count[a[i]]] = a[i];
}
return b;
}
}
약 2N번의 비교와 1번의 전체 복사가 있는 정도여서 속도는 빠르다.
하지만, 입력자료의 범위가 아주 넓을 때는 메모리 소모가 너무 커서 아주 느린 성능을 보인다.
분포수 세기 알고리즘은 기수 정렬에서 사용되어 강력한 기능을 발휘하므로 눈여겨 볼 필요가 있다.